A <#206#>pair<#206#> (sometimes called a <#207#>dotted pair<#207#>) is a record structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure <#208#>cons<#208#>. The car and cdr fields are accessed by the procedures <#209#>car<#209#> and <#210#>cdr<#210#>. The car and cdr fields are assigned by the procedures <#211#>set-car!<#211#> and <#212#>set-cdr!<#212#>.
Pairs are used primarily to represent lists. A list can
be defined recursively as either the empty list
The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two-element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.
The empty list<#222#>empty list<#222#> is a special object of its own type (it is not a pair); it has no elements and its length is zero.
The most general notation (external representation) for Scheme pairs is the ``dotted'' notation <#2023#>(<#225#>c<#225#> . <#226#>c<#226#>)<#2023#> where <#227#>c<#227#> is the value of the car field and <#228#>c<#228#> is the value of the cdr field. For example <#229#>(4 . 5)<#229#> is a pair whose car is 4 and whose cdr is 5. Note that <#230#>(4 . 5)<#230#> is the external representation of a pair, not an expression that evaluates to a pair.
A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces. The
empty list
and
are equivalent notations for a list of symbols.
A chain of pairs not ending in the empty list is called an <#237#>improper list<#237#>. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:
is equivalent to
Whether a given pair is a list depends upon what is stored in the cdr field. When the <#242#>set-cdr!<#242#> procedure is used, an object can be a list one moment and not the next:
Within literal expressions and representations of objects read by the
<#245#>read<#245#> procedure, the forms <#246#>datum<#246#><#247#>'<#247#>,
<#248#>datum<#248#>, <#249#>,<#249#><#250#>datum<#250#><#251#>,<#251#>, and
<#252#>,@<#252#><#253#>datum<#253#> denote two-element lists whose first elements are
the symbols <#254#>quote<#254#>, <#255#>quasiquote<#255#>, <#2024#><#256#>unquote<#256#><#2024#>, and
<#257#>unquote-splicing<#257#>, respectively. The second element in each case
is <#258#>datum<#258#>. This convention is supported so that arbitrary Scheme
programs may be represented as lists. <#259#>Can or need this be stated
more carefully?<#259#> That is, according to Scheme's grammar, every
<#260#>expression<#260#> is also a <#261#>datum<#261#> (see section~#datum#262>
0<#2035#>(cadr <#325#>pair<#325#>)<#2035#> 1<#326#>essential procedure<#326#>